#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int searchInsert(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (target == nums[mid])
            return mid;
        else if (target >= nums[mid])
            left = mid + 1;
        else
            right = mid - 1;
    }
    if (nums[mid] > target)
        return mid;
    else
        return mid + 1;
}
int main()
{
    int arr[] = { 1,3,5,6 };
    printf("%d", searchInsert(arr, 4, 5));
	return 0;
}